package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2022-01-13 08:29
 * @description: Functions of this class is
 * 官方题解（普通动态规划）：
 * class Solution {
 *     public int integerBreak(int n) {
 *         int dp[]=new int[n+1];
 *         dp[0]=dp[1]=0;//0和1都不能拆分
 *         for(int i=2;i<=n;i++){
 *             int curMax=dp[i];
 *             for(int j=0;j<i;j++){
 *                 curMax=Math.max(curMax,Math.max(j*(i-j),dp[i-j]*j));//判断拆分（i-j）这个数字所带来收益大，还是不拆分收益大
 *             }
 *             dp[i]=curMax;
 *         }
 *         return dp[n];
 *     }
 * }
 * -------------------------------------------------------
 * 官方题解（优化的动态规划）：
 * class Solution {
 *     public int integerBreak(int n) {
 *         if (n < 4) {
 *             return n - 1;
 *         }
 *         int[] dp = new int[n + 1];
 *         dp[2] = 1;
 *         for (int i = 3; i <= n; i++) {
 *         //如果 j≥4，则 dp[j]≥j
 *         //通过一些数学的推导，判断到j >=4的情况都是不需要考虑的，
 *         //计算dp[i] 的值只需要考虑 j=2 和 j=3 的情况
 *             dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
 *         }
 *         return dp[n];
 *     }
 * }
 * ----------------------------------------------------------
 * 剪绳子II（需要对答案取模）：
 * class Solution {
 *     public int cuttingRope(int n) {
 *         if(n<4){
 *             return n-1;
 *         }
 *         long sum=1;
 *         while(n>4){
 *             sum=sum*3%1000000007
 *             n-=3;
 *         }
 *         return (int)(sum*n%1000000007);//结尾这里一定要乘一个n！！！！！！！！！！！！！！！！别忘了！！！！！！！！！！
 *     }
 * }
 **/
public class NoNoNoNo剪绳子II整数拆分 {
}